package chapter03;

import java.util.ArrayList;
import java.util.List;

public class Flatten114 {
    /**
     * 先序遍历
     * 先序遍历将遍历节点保存在数组中
     * 遍历数组 i->[0,length)
     *      pre记录前一个节点 cur为当前节点 只需将cur赋值给pre的右孩子 pre左孩子为null cur再赋值给pre 循环即可
     */
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
    }

    List<TreeNode> nodes;
    public void flatten(TreeNode root) {
        if(root==null){
            return;
        }
        nodes=new ArrayList<>();
        process(root);
        int len=nodes.size();
        TreeNode pre=null;
        for(int i=0;i<len;i++){
            TreeNode cur=nodes.get(i);
            if(pre!=null){
                pre.left=null;
                pre.right=cur;
            }
            pre=cur;
        }
    }

    public void process(TreeNode x){
        if(x==null){
            return;
        }
        nodes.add(x);
        process(x.left);
        process(x.right);
    }
}
